#!/usr/bin/env python
# -*- coding: utf-8 -*-

# @Time     :2020/11/26
# @Author   :Changshu
# @File     :Exercise_496.py

# 496. 下一个更大元素 I
# 给定两个 没有重复元素 的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。找到 nums1 中每个元素在 nums2 中的下一个比其大的值。
#
# nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在，对应位置输出 -1 。
#
# nums1和nums2中所有元素是唯一的。
# nums1和nums2 的数组大小都不超过1000。

'''法一，先从nums2中计算出每一个元素的更大值'''
def nextGreaterElement(nums1: list, nums2: list) -> list:
	d={}
	stack=[]
	for n in nums2:
		while len(stack)!=0 and n>stack[-1]:
			d[stack[-1]]=n
			stack.pop()
		stack.append(n)
	while len(stack)!=0:
		n=stack.pop()
		d[n]=-1
	for n in nums1:
		stack.append(d[n])
	return stack

if __name__ == '__main__':
	# nums1=[4,1,2]
	# nums1=[2,4]
	nums1=[7,5,3,6,4]
	# nums2=[1,3,4,2]
	# nums2=[1,2,3,4]
	nums2=[8,9,5,10,7,3,4,6,11,2]
	print(nextGreaterElement(nums1,nums2))